{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Subarrays With Median K"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countSubarrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计中位数为 K 的子数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个长度为 <code>n</code> 的数组 <code>nums</code> ，该数组由从 <code>1</code> 到 <code>n</code> 的 <strong>不同</strong> 整数组成。另给你一个正整数 <code>k</code> 。</p>\n",
    "\n",
    "<p>统计并返回 <code>nums</code> 中的 <strong>中位数</strong> 等于 <code>k</code> 的非空子数组的数目。</p>\n",
    "\n",
    "<p><strong>注意：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>数组的中位数是按 <strong>递增</strong> 顺序排列后位于 <strong>中间</strong> 的那个元素，如果数组长度为偶数，则中位数是位于中间靠 <strong>左</strong> 的那个元素。\n",
    "\n",
    "\t<ul>\n",
    "\t\t<li>例如，<code>[2,3,1,4]</code> 的中位数是 <code>2</code> ，<code>[8,4,3,5,1]</code> 的中位数是 <code>4</code> 。</li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "\t<li>子数组是数组中的一个连续部分。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [3,2,1,4,5], k = 4\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>中位数等于 4 的子数组有：[4]、[4,5] 和 [1,4,5] 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2,3,1], k = 3\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>[3] 是唯一一个中位数等于 3 的子数组。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i], k &lt;= n</code></li>\n",
    "\t<li><code>nums</code> 中的整数互不相同</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-subarrays-with-median-k](https://leetcode.cn/problems/count-subarrays-with-median-k/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-subarrays-with-median-k](https://leetcode.cn/problems/count-subarrays-with-median-k/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,2,1,4,5]\\n4', '[2,3,1]\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        sisa_lens: List[int] = []\n",
    "        sisa_len: int = 1\n",
    "            \n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] > nums[i - 1]:\n",
    "                sisa_len += 1\n",
    "            else:\n",
    "                sisa_lens.append(sisa_len)\n",
    "                sisa_len = 1\n",
    "        sisa_lens.append(sisa_len)\n",
    "        \n",
    "        return sum((1 + n) * n // 2 for n in sisa_lens)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        res, i = n, 0\n",
    "        while i < n:\n",
    "            j, cnt = i, 0\n",
    "            while j + 1 < n and nums[j] < nums[j + 1]:\n",
    "                j += 1\n",
    "                cnt += 1\n",
    "            res += cnt + cnt * (cnt - 1) // 2\n",
    "            i = j + 1\n",
    "        return res            \n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        count = 1\n",
    "        pre = 1\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] > nums[i - 1]:\n",
    "                pre += 1\n",
    "            else:\n",
    "                pre = 1\n",
    "            count += pre\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        cur, res = 1,1\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i]<=nums[i-1]:\n",
    "                cur = 1\n",
    "            else:\n",
    "                cur+=1\n",
    "            res+=cur\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        res, i = n, 0\n",
    "        while i < n:\n",
    "            j, cnt = i, 0\n",
    "            while j + 1 < n and nums[j] < nums[j + 1]:\n",
    "                j += 1\n",
    "                cnt += 1\n",
    "            res += cnt + cnt * (cnt - 1) // 2\n",
    "            i = j + 1\n",
    "        return res            \n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        temp = 0\n",
    "        allTemp = 1\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] <= nums[i - 1]:\n",
    "                temp = 0\n",
    "            else:\n",
    "                temp += 1\n",
    "            allTemp += temp + 1\n",
    "        return allTemp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        final_count = 1\n",
    "        count = 1\n",
    "\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i] > nums[i-1]:\n",
    "                count += 1\n",
    "            else:\n",
    "                count = 1\n",
    "            final_count += count\n",
    "        return final_count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        res, i = n, 0\n",
    "        while i < n:\n",
    "            j, cnt = i, 0\n",
    "            while j + 1 < n and nums[j] < nums[j + 1]:\n",
    "                j += 1\n",
    "                cnt += 1\n",
    "            res += cnt + cnt * (cnt - 1) // 2\n",
    "            i = j + 1\n",
    "        return res            \n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "      a = 0\n",
    "      b = 0\n",
    "      pre = inf\n",
    "      for num in nums:\n",
    "        if num > pre: a += 1\n",
    "        else: a = 1\n",
    "        pre = num\n",
    "        b += a\n",
    "      return b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        res = dp = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            dp = dp + 1 if i == 0 or num > nums[i - 1] else 1\n",
    "            res += dp\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\r\n",
    "        count = 1\r\n",
    "        pre = 1\r\n",
    "        for i in range(1, len(nums)):\r\n",
    "            if nums[i] > nums[i - 1]:\r\n",
    "                pre += 1\r\n",
    "            else:\r\n",
    "                pre = 1\r\n",
    "            count += pre\r\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        result, cur, prev = 0, 0, float('inf')\n",
    "        for x in nums:\n",
    "            result += (cur := cur + 1 if prev < x else 1)\n",
    "            prev = x\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        cur, pre = 0, float('inf')\n",
    "        return sum((cur := cur + 1 if (-pre + (pre := x)) > 0 else 1) for x in nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 遍历\n",
    "    def countSubarrays1(self, nums: List[int]) -> int:\n",
    "        ans = 1\n",
    "        cur = 1\n",
    "        for x,y in pairwise(nums):\n",
    "            if y > x:\n",
    "                cur += 1\n",
    "            else:\n",
    "                cur = 1\n",
    "\n",
    "            ans += cur\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "    # 遍历2\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        count = 1\n",
    "        pre = 1\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] > nums[i - 1]:\n",
    "                pre += 1\n",
    "            else:\n",
    "                pre = 1\n",
    "\n",
    "            count += pre\n",
    "\n",
    "        return count\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        count = 1\n",
    "        pre = 1\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] > nums[i - 1]:\n",
    "                pre += 1\n",
    "            else:\n",
    "                pre = 1\n",
    "            count += pre\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        count = 1  # 因为数组的第一个元素自身就是一个子数组\n",
    "        pre = 1  # 记录前一个数字的严格递增子数组的长度\n",
    "\n",
    "        # 从数组的第二个元素开始遍历\n",
    "        for i in range(1, len(nums)):\n",
    "            # 如果当前元素大于前一个元素，说明它可以构成新的递增子数组\n",
    "            if nums[i] > nums[i - 1]:\n",
    "                pre += 1\n",
    "            # 否则，重置 pre 为1\n",
    "            else:\n",
    "                pre = 1\n",
    "            # 累加 pre 到 count\n",
    "            count += pre\n",
    "\n",
    "        return count\n",
    "\n",
    "# 示例\n",
    "solution = Solution()\n",
    "nums1 = [1,3,5,4,4,6]\n",
    "print(solution.countSubarrays(nums1))  # 输出: 10\n",
    "\n",
    "nums2 = [1,2,3,4,5]\n",
    "print(solution.countSubarrays(nums2))  # 输出: 15\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 遍利\n",
    "    def countSubarrays1(self, nums: List[int]) -> int:\n",
    "        ans = 1\n",
    "        cur = 1\n",
    "        for x,y in pairwise(nums):\n",
    "            if y > x:\n",
    "                cur += 1\n",
    "            else:\n",
    "                cur = 1\n",
    "\n",
    "            ans += cur\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        count = 1\n",
    "        pre = 1\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] > nums[i - 1]:\n",
    "                pre += 1\n",
    "            else:\n",
    "                pre = 1\n",
    "\n",
    "            count += pre\n",
    "\n",
    "        return count\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 遍历\n",
    "    def countSubarrays1(self, nums: List[int]) -> int:\n",
    "        ans = 1\n",
    "        cur = 1\n",
    "        for x,y in pairwise(nums):\n",
    "            if y > x:\n",
    "                cur += 1\n",
    "            else:\n",
    "                cur = 1\n",
    "\n",
    "            ans += cur\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "    # 遍历2\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        count = 1\n",
    "        cur = 1\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] > nums[i - 1]:\n",
    "                cur += 1\n",
    "            else:\n",
    "                cur = 1\n",
    "\n",
    "            count += cur\n",
    "\n",
    "        return count\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 便利\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        ans = 1\n",
    "        cur = 1\n",
    "        for x,y in pairwise(nums):\n",
    "            if y > x:\n",
    "                cur += 1\n",
    "            else:\n",
    "                cur = 1\n",
    "\n",
    "            ans += cur\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        dp=[1]*n\n",
    "        for i in range(1,n):\n",
    "            if nums[i]>nums[i-1]:\n",
    "                dp[i]+=dp[i-1]\n",
    "        return sum(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        dp=[1]*n\n",
    "\n",
    "        for i in range(1,n):\n",
    "            if nums[i]>nums[i-1]:\n",
    "                dp[i]=dp[i-1]+1\n",
    "\n",
    "        \n",
    "        return sum(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        dp=[0]*n\n",
    "        dp[0]=1\n",
    "        for i in range(1,n):\n",
    "            if nums[i]>nums[i-1]:\n",
    "                dp[i]=dp[i-1]+1\n",
    "            else:\n",
    "                dp[i]=1\n",
    "        return sum(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        dp=[0]*n\n",
    "        dp[0]=1\n",
    "        for i in range(1,n):\n",
    "            if nums[i]>nums[i-1]:\n",
    "                dp[i]=max(dp[i],dp[i-1]+1)\n",
    "            else:\n",
    "                dp[i]=1\n",
    "        return sum(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        dp=[0]*n\n",
    "        dp[0]=1\n",
    "        for i in range(1,n):\n",
    "            if nums[i]>nums[i-1]:\n",
    "                dp[i]=dp[i-1]+1\n",
    "            else:\n",
    "                dp[i]=1\n",
    "        return sum(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        dp=[1]*n\n",
    "        for i in range(1,n):\n",
    "            if nums[i]>nums[i-1]:\n",
    "                dp[i]+=dp[i-1]\n",
    "        return sum(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        dp=[1]*n\n",
    "        for i in range(1,n):\n",
    "            if nums[i]>nums[i-1]:\n",
    "                dp[i]+=dp[i-1]\n",
    "        return sum(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        dp=[1]*n\n",
    "        for i in range(1,n):\n",
    "            if nums[i]>nums[i-1]:\n",
    "                dp[i]=dp[i-1]+1\n",
    "        return sum(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        #因为有无后效性,线性DP即可\n",
    "        n=len(nums)\n",
    "        dp=[1]*n\n",
    "        ans=1\n",
    "        for i in range(1,n):\n",
    "            if nums[i]>nums[i-1]:\n",
    "                dp[i]=dp[i-1]+1\n",
    "            ans+=dp[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        #DP\n",
    "        n=len(nums)\n",
    "        dp=[1]*n\n",
    "        ans=1\n",
    "        for i in range(1,n):\n",
    "            if nums[i]>nums[i-1]:\n",
    "                dp[i]=dp[i-1]+1\n",
    "            ans+=dp[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        ans =0\n",
    "        min_i =max_i =i0=-1\n",
    "        for i,x in enumerate(nums):\n",
    "            if x==minK:\n",
    "                min_i =i\n",
    "            if x==maxK:\n",
    "                max_i = i\n",
    "            if not minK<=x<=maxK:\n",
    "                i0=i\n",
    "\n",
    "            ans+= max(min(min_i,max_i)-i0,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], min_k: int, max_k: int) -> int:\n",
    "        # 双指针：\n",
    "        ans = 0\n",
    "        min_i = max_i = i0 = -1\n",
    "        for i, x in enumerate(nums):\n",
    "            if x == min_k: min_i = i\n",
    "            if x == max_k: max_i = i\n",
    "            if not min_k <= x <= max_k: i0 = i\n",
    "            ans += max(min(min_i, max_i) - i0, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        res = 0\n",
    "        min_i,max_i,i0 = -1,-1,-1\n",
    "        for i,x in enumerate(nums):\n",
    "            # 记录下最近出现过的minK和maxK位置\n",
    "            if x == minK : \n",
    "                min_i = i\n",
    "            if x == maxK:\n",
    "                max_i = i\n",
    "            if not minK <= x <= maxK:\n",
    "                i0 = i\n",
    "            # 如果min(min_i,max_i)-io < 0,则说明在i0右侧minK和maxK没有同时出现\n",
    "            # 综上max(min(max_i,max_i) - i0, 0)表示的是以i为右端点的符合条件的子数组\n",
    "            res += max(min(min_i,max_i) - i0, 0)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], min_k: int, max_k: int) -> int:\n",
    "        ans = 0\n",
    "        min_i = max_i = i0 = -1\n",
    "        for i, x in enumerate(nums):\n",
    "            if x == min_k: min_i = i\n",
    "            if x == max_k: max_i = i\n",
    "            if not min_k <= x <= max_k: i0 = i  # 子数组不能包含 nums[i0]\n",
    "            ans += max(min(min_i, max_i) - i0, 0)\n",
    "            # 注：上面这行代码，改为手动算 min max 会更快\n",
    "            # j = min_i if min_i < max_i else max_i\n",
    "            # if j > i0: ans += j - i0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        n = len(nums)\n",
    "        pre = 0\n",
    "        minn, maxx = -1, -1\n",
    "        ans = 0\n",
    "        \n",
    "        for i, x in enumerate(nums):\n",
    "            if x == minK:\n",
    "                minn = i\n",
    "            if x == maxK:\n",
    "                maxx = i\n",
    "            if x < minK or x > maxK:\n",
    "                pre = i + 1\n",
    "            ans += max(0, min(minn, maxx) - pre + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        n = len(nums)\n",
    "        start_point = 0\n",
    "        idx = ans = 0\n",
    "        min_pos = max_pos = -1\n",
    "\n",
    "        while idx < n:\n",
    "            if nums[idx] < minK or nums[idx] > maxK:\n",
    "                idx += 1\n",
    "                start_point = idx\n",
    "                continue\n",
    "            if nums[idx] == minK:\n",
    "                min_pos = idx\n",
    "            if nums[idx] == maxK:\n",
    "                max_pos = idx\n",
    "            ans += max(min(min_pos, max_pos) - start_point + 1, 0)\n",
    "            idx += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        minI = -1\n",
    "        maxI = -1\n",
    "        curI = -1\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            val = nums[i]\n",
    "            if val > maxK or val < minK:\n",
    "                curI = i\n",
    "\n",
    "            if val == maxK:\n",
    "                maxI = i\n",
    "\n",
    "            if val == minK:\n",
    "                minI = i\n",
    "\n",
    "            ans += max(min(maxI, minI) - curI, 0)\n",
    "\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        offMinK = offMaxK = -1\n",
    "        left = 0\n",
    "        res = 0\n",
    "        for i, n in enumerate(nums):\n",
    "            if n < minK or n > maxK:\n",
    "                left = i + 1\n",
    "            else:\n",
    "                if n == minK:\n",
    "                    offMinK = i\n",
    "                if n == maxK:\n",
    "                    offMaxK = i\n",
    "            if left <= min(offMinK, offMaxK):\n",
    "                res += min(offMinK, offMaxK) - left + 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        ans = 0 \n",
    "        min_i = max_i = i0 = -1\n",
    "        for i, x in enumerate(nums):\n",
    "            if x == minK:\n",
    "                min_i = i \n",
    "            if x == maxK:\n",
    "                max_i = i \n",
    "            if not minK <= x <= maxK:\n",
    "                i0 = i \n",
    "            ans += max(min(min_i, max_i) - i0, 0)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        l = minI = maxI = -1\n",
    "        count = 0 \n",
    "        for i , num in enumerate(nums):\n",
    "            if num > maxK or num < minK: l = i \n",
    "            if num == maxK : maxI = i \n",
    "            if num == minK : minI = i \n",
    "            \n",
    "            count += max(min(minI, maxI) - l , 0) \n",
    "            \n",
    "\n",
    "        \n",
    "        return count\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# count子数组\n",
    "# 枚举右端点作为子区间右端点的情况 \n",
    "# 将使区间不符合性质的上一个点作为左端点\n",
    "# 判断在这种情况下从左端点到右端点符合性质的子区间个数\n",
    "# 有两个性质点 所以需要两个下标来统计\n",
    "# 两个性质点如果有一个小于左端点 那么则个数为0 如果都大于左端点 那么则为小的那个减去左端点"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        r1=-1\n",
    "        r2=-1\n",
    "        l=-1\n",
    "        ans=0\n",
    "        for i,v in enumerate(nums):\n",
    "            if v==minK:\n",
    "                r1=i\n",
    "            if v==maxK:\n",
    "                r2=i\n",
    "            if v<minK or v > maxK:\n",
    "                l=i\n",
    "            ans+=max(0,min(r1,r2)-l)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], min_k: int, max_k: int) -> int:\n",
    "        ans = 0\n",
    "        min_i = max_i = i0 = -1\n",
    "        for i, x in enumerate(nums):\n",
    "            if x == min_k: min_i = i\n",
    "            if x == max_k: max_i = i\n",
    "            if not min_k <= x <= max_k: i0 = i  # 子数组不能包含 nums[i0]\n",
    "            ans += max(min(min_i, max_i) - i0, 0)\n",
    "            # 注：上面这行代码，改为手动算 min max 会更快\n",
    "            # j = min_i if min_i < max_i else max_i\n",
    "            # if j > i0: ans += j - i0\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        minIdx = -1\n",
    "        maxIdx = -1\n",
    "\n",
    "        start = -1\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] < minK or nums[i] > maxK:\n",
    "                start = -1\n",
    "                minIdx = -1\n",
    "                maxIdx = -1\n",
    "                continue\n",
    "\n",
    "            if start == -1:\n",
    "                start = i \n",
    "\n",
    "\n",
    "\n",
    "            if nums[i] == minK:\n",
    "                minIdx = i \n",
    "            \n",
    "            if nums[i] == maxK:\n",
    "                maxIdx = i\n",
    "            \n",
    "            \n",
    "            if nums[i] == minK:\n",
    "                if maxIdx == -1:\n",
    "                    pass\n",
    "                else:\n",
    "                    ans += maxIdx - start + 1\n",
    "            elif nums[i] == maxK:\n",
    "                if minIdx == -1:\n",
    "                    pass\n",
    "                else:\n",
    "                    ans += minIdx - start + 1\n",
    "            else: # middle\n",
    "                if maxIdx == -1 or minIdx == -1:\n",
    "                    pass\n",
    "                else:\n",
    "                    ans += min(maxIdx, minIdx) - start + 1 \n",
    "\n",
    "\n",
    "\n",
    "                   \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        minIdx = -1\n",
    "        maxIdx = -1\n",
    "\n",
    "        start = -1\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] < minK or nums[i] > maxK:\n",
    "                start = -1\n",
    "                minIdx = -1\n",
    "                maxIdx = -1\n",
    "                continue\n",
    "\n",
    "            if start == -1:\n",
    "                start = i \n",
    "            \n",
    "            if nums[i] == minK:\n",
    "                if maxIdx == -1:\n",
    "                    pass\n",
    "                else:\n",
    "                    ans += maxIdx - start + 1\n",
    "            elif nums[i] == maxK:\n",
    "                if minIdx == -1:\n",
    "                    pass\n",
    "                else:\n",
    "                    ans += minIdx - start + 1\n",
    "            else: # middle\n",
    "                if maxIdx == -1 or minIdx == -1:\n",
    "                    pass\n",
    "                else:\n",
    "                    ans += min(maxIdx, minIdx) - start + 1 \n",
    "\n",
    "            if nums[i] == minK == maxK:\n",
    "                ans += 1\n",
    "\n",
    "            if nums[i] == minK:\n",
    "                minIdx = i \n",
    "            \n",
    "            if nums[i] == maxK:\n",
    "                maxIdx = i\n",
    "\n",
    "                   \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\r\n",
    "        if minK > maxK: return 0\r\n",
    "        res = 0\r\n",
    "        lastInvalid = lastmaxK = lastminK = -1\r\n",
    "\r\n",
    "        for i, num in enumerate(nums):\r\n",
    "            if num > maxK or num < minK:\r\n",
    "                lastInvalid = i\r\n",
    "            else:\r\n",
    "                if num == minK:\r\n",
    "                    lastminK = i\r\n",
    "                if num == maxK:\r\n",
    "                    lastmaxK = i\r\n",
    "\r\n",
    "            res += max(0, min(lastminK, lastmaxK) - lastInvalid)\r\n",
    "        \r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        ans=0\n",
    "        min_i=max_i=i0=-1\n",
    "        for idx,x in enumerate(nums):\n",
    "            if x==minK:\n",
    "                min_i=idx\n",
    "            if x==maxK:\n",
    "                max_i=idx\n",
    "            if x<minK or x>maxK:\n",
    "                i0=idx\n",
    "            j=min_i if min_i<max_i else max_i\n",
    "            if j>i0:\n",
    "                ans+=j-i0\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        qmn = Deque() # 区间最小值对应的下标\n",
    "        qmx = Deque() # 区间最大值对应的下标\n",
    "        l = r = 0     # 区间左右端点\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        while r < n:\n",
    "            while qmn and nums[r] <= nums[qmn[-1]]:\n",
    "                qmn.pop()\n",
    "            qmn.append(r)\n",
    "            while qmx and nums[r] >= nums[qmx[-1]]:\n",
    "                qmx.pop()\n",
    "            qmx.append(r)\n",
    "            if nums[qmn[0]] == minK and nums[qmx[0]] == maxK:\n",
    "                ans += min(qmn[0], qmx[0]) - l + 1\n",
    "            # 当前[l,r]状态下的区间最小值小于 minK 或者 区间最大值大于maxK \n",
    "            # 不符合要求, 需要缩小窗口, 缩小窗口同时更新qmn 和 qmx \n",
    "            while (qmn and nums[qmn[0]] < minK) or (qmx and nums[qmx[0]] > maxK):\n",
    "                l += 1\n",
    "                if qmn and qmn[0] < l:\n",
    "                    qmn.popleft()\n",
    "                if qmx and qmx[0] < l:\n",
    "                    qmx.popleft()\n",
    "            r += 1\n",
    "        return ans\n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        ret = 0\n",
    "        n = len(nums)\n",
    "        minidx = maxidx = -1\n",
    "        bad = -1\n",
    "        for i in range(n):\n",
    "            if nums[i] > maxK or nums[i] < minK:\n",
    "                bad = i\n",
    "                minidx = maxidx = -1\n",
    "                continue\n",
    "            \n",
    "            if nums[i] == minK:\n",
    "                minidx = i\n",
    "            if nums[i] == maxK:\n",
    "                maxidx = i\n",
    "            if minidx != -1 and maxidx != -1:\n",
    "                ret += min(minidx, maxidx) - bad\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countSubarrays(self, nums: List[int], min_k: int, max_k: int) -> int:\r\n",
    "        ans = 0\r\n",
    "        min_i = max_i = i0 = -1\r\n",
    "        for i, x in enumerate(nums):\r\n",
    "            if x == min_k: min_i = i\r\n",
    "            if x == max_k: max_i = i\r\n",
    "            if not min_k <= x <= max_k: i0 = i  # 子数组不能包含 nums[i0]\r\n",
    "            ans += max(min(min_i, max_i) - i0, 0)\r\n",
    "            # 注：上面这行代码，改为手动算 min max 会更快\r\n",
    "            # j = min_i if min_i < max_i else max_i\r\n",
    "            # if j > i0: ans += j - i0\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        \"\"\" Sliding Window \"\"\" \n",
    "\n",
    "        lb = -1 \n",
    "        n = len(nums) \n",
    "        id_min, id_max = -1, -1 \n",
    "        ans = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            if nums[i] == minK:\n",
    "                id_min = i \n",
    "            if nums[i] == maxK:\n",
    "                id_max = i \n",
    "            if not (minK <= nums[i] <= maxK):\n",
    "                lb = i\n",
    "            \n",
    "            ans += max(min(id_min,id_max) - lb, 0)\n",
    "            \n",
    "\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def countSubarrays(self, nums: List[int], min_k: int, max_k: int) -> int:\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        min_i = max_i = i0 = -1\n",
    "\n",
    "        for i, x in enumerate(nums):\n",
    "\n",
    "            if x == min_k: min_i = i\n",
    "\n",
    "            if x == max_k: max_i = i\n",
    "\n",
    "            if not min_k <= x <= max_k: i0 = i  # 子数组不能包含 nums[i0]\n",
    "\n",
    "            ans += max(min(min_i, max_i) - i0, 0)\n",
    "\n",
    "            # 注：上面这行代码，改为手动算 min max 会更快\n",
    "\n",
    "            # j = min_i if min_i < max_i else max_i\n",
    "\n",
    "            # if j > i0: ans += j - i0\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        \"\"\" Sliding Window \"\"\" \n",
    "\n",
    "        lb = -1 \n",
    "        n = len(nums) \n",
    "        id_min, id_max = -float('inf'), -float('inf')\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            if nums[i] == minK:\n",
    "                id_min = i \n",
    "            if nums[i] == maxK:\n",
    "                id_max = i \n",
    "            if not (minK <= nums[i] <= maxK):\n",
    "                lb = i\n",
    "            \n",
    "            if lb < min(id_min,id_max):\n",
    "                ans += min(id_min,id_max) - lb\n",
    "\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        \n",
    "                    \n",
    "                        ans = 0\n",
    "                        minI = maxI = i0 = -1\n",
    "                        for i,x in enumerate(nums):\n",
    "                            if minK == x:minI = i\n",
    "                            if maxK == x:maxI = i\n",
    "                            if not minK <= x <= maxK:i0 = i\n",
    "                            ans += max(min(minI,maxI) - i0,0)\n",
    "                        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        # ans = 0 \n",
    "        # min_i = max_i = i0 =-1\n",
    "        # for i,x in enumerate(nums):\n",
    "        #     if x == minK: min_i =i\n",
    "        #     if x == maxK: max_i =i \n",
    "        #     if x < minK or x > maxK :i0 =i \n",
    "        #     j = min_i if min_i < max_i else max_i\n",
    "        #     # ans += max(min(min_i,max_i)-i0,0)\n",
    "        #     if j > i0: ans += j -i0\n",
    "        # return ans \n",
    "\n",
    "        ans = 0 \n",
    "        min_i = max_i = i0 = -1 \n",
    "        for i ,x in enumerate(nums):\n",
    "            if x == minK : min_i =i \n",
    "            if x == maxK: max_i = i \n",
    "            if x < minK or x > maxK : i0 = i  \n",
    "            j = min_i if min_i < max_i else max_i\n",
    "            if j > i0: ans += j-i0 \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        qmn = Deque()\n",
    "        qmx = Deque()\n",
    "        l = r = 0\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        while r < n:\n",
    "            while qmn and nums[r] <= nums[qmn[-1]]:\n",
    "                qmn.pop()\n",
    "            qmn.append(r)\n",
    "            while qmx and nums[r] >= nums[qmx[-1]]:\n",
    "                qmx.pop()\n",
    "            qmx.append(r)\n",
    "            if nums[qmn[0]] == minK and nums[qmx[0]] == maxK:\n",
    "                ans += min(qmn[0], qmx[0]) - l + 1\n",
    "            while (qmn and nums[qmn[0]] < minK) or (qmx and nums[qmx[0]] > maxK):\n",
    "                l += 1\n",
    "                if qmn and qmn[0] < l:\n",
    "                    qmn.popleft()\n",
    "                if qmx and qmx[0] < l:\n",
    "                    qmx.popleft()\n",
    "            r += 1\n",
    "        return ans\n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "\"\"\" \n",
    "先考虑子数组中都是[minK, maxK]范围内的数的情况，这时合法的区间应包括minK和maxK，假设当前下标为右端点，则合法的左端点数量应为min(minI, maxI) + 1，其中minI表示左侧第一次出现minK的下标，同理maxI表示左侧第一次出现maxK的下标，两个边界值minK、maxK都要出现，所以是取下标的较小值min(minI, maxI)。\n",
    "由于子数组中不一定都是[minK, maxK]范围的数，所以可以用一个下标维护最后一个不是[minK, maxK]范围数的下标i0，则枚举每个右侧端点时，左侧端点的有效范围对应的数量为：min(minI, maxI) - i0，而当min(minI, maxI) < i0时，表示有效范围内不包含两个边界值，也即有效的左侧端点数量为零，这种情况跟0取max即可：最终累加答案为max(min(minI, maxI) - i0, 0)。\n",
    "\"\"\"\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        i0 = minI = maxI = -1\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            if x < minK or x > maxK:\n",
    "                i0 = i\n",
    "                continue\n",
    "            if x == minK:\n",
    "                minI = i\n",
    "            if x == maxK:\n",
    "                maxI = i\n",
    "            ans += max(min(minI, maxI) - i0, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        if minK>maxK:\n",
    "            return 0\n",
    "        l,h=-1,-1\n",
    "        left=0\n",
    "        n=len(nums)\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            if nums[i]==minK:\n",
    "                l=i\n",
    "            if nums[i]==maxK:\n",
    "                h=i\n",
    "            if nums[i]<minK or nums[i]>maxK:\n",
    "                l=-1\n",
    "                h=-1\n",
    "                left=i+1\n",
    "            if l!=-1 and h!=-1:\n",
    "                ans+=min(l,h)-left+1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        res = 0\n",
    "        l = -1\n",
    "        minKIndex = maxKIndex = -1\n",
    "\n",
    "        for r in range(len(nums)):\n",
    "            if nums[r] == minK:\n",
    "                minKIndex = r\n",
    "            if nums[r] == maxK:\n",
    "                maxKIndex = r\n",
    "            if nums[r] > maxK or nums[r] < minK:\n",
    "                l = r\n",
    "            res += max(min(minKIndex,maxKIndex) - l, 0)\n",
    "            \n",
    "        return res\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        minI, maxI, i0 = -1, -1, -1\n",
    "        ans = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            if x == minK:\n",
    "                minI = i\n",
    "            if x == maxK:\n",
    "                maxI = i\n",
    "            if not minK <= x <= maxK:\n",
    "                i0 = i\n",
    "            ans += max(min(minI, maxI) - i0, 0)\n",
    "        return ans\n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "            \n",
    "1\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        n = len(nums)\n",
    "        leftMax = - 1\n",
    "        leftMin = - 1\n",
    "        leftBound = - 1 \n",
    "        res = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            if num == minK:\n",
    "                leftMin = i \n",
    "            if num == maxK:\n",
    "                leftMax = i \n",
    "            if num < minK or num > maxK:\n",
    "                leftBound = i \n",
    "            res += max(0, min(leftMin, leftMax) - leftBound)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        ans=0\n",
    "        imax=-1\n",
    "        imin=-1\n",
    "        i0=-1\n",
    "        n=len(nums)\n",
    "        for i,x in enumerate(nums):\n",
    "            if x==minK:\n",
    "                imin=i\n",
    "            if x==maxK:\n",
    "                imax=i\n",
    "            if x<minK or x>maxK:\n",
    "                i0=i\n",
    "            ans+=max(min(imax,imin)-i0,0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        n = len(nums)\n",
    "        leftMin, leftMax, leftBound = - 1, - 1, - 1\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if nums[i] == minK:\n",
    "                leftMin = i\n",
    "            if nums[i] == maxK:\n",
    "                leftMax = i\n",
    "            if nums[i] > maxK or nums[i] < minK:\n",
    "                leftBound = i \n",
    "            res += max(min(leftMin, leftMax) - leftBound, 0)\n",
    "        return res \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        # ans = 0 \n",
    "        # min_i = max_i = i0 =-1\n",
    "        # for i,x in enumerate(nums):\n",
    "        #     if x == minK: min_i =i\n",
    "        #     if x == maxK: max_i =i \n",
    "        #     if x < minK or x > maxK :i0 =i \n",
    "        #     j = min_i if min_i < max_i else max_i\n",
    "        #     # ans += max(min(min_i,max_i)-i0,0)\n",
    "        #     if j > i0: ans += j -i0\n",
    "        # return ans \n",
    "\n",
    "        ans = 0 \n",
    "        min_i = max_i = i0 = -1 \n",
    "        for i ,x in enumerate(nums):\n",
    "            if x == minK : min_i =i \n",
    "            if x == maxK: max_i = i \n",
    "            if x < minK or x > maxK : i0 = i  \n",
    "            j = min_i if min_i < max_i else max_i\n",
    "            if j > i0: ans += j-i0 \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        ans = 0 \n",
    "        min_i = max_i = i0 =-1\n",
    "        for i,x in enumerate(nums):\n",
    "            if x == minK: min_i =i\n",
    "            if x == maxK: max_i =i \n",
    "            if x < minK or x > maxK :i0 =i \n",
    "            j = min_i if min_i < max_i else max_i\n",
    "            # ans += max(min(min_i,max_i)-i0,0)\n",
    "            if j > i0: ans += j -i0\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        ans = 0 \n",
    "        min_i = max_i = i0 =-1\n",
    "        for i,x in enumerate(nums):\n",
    "            if x == minK: min_i =i\n",
    "            if x == maxK: max_i =i \n",
    "            if x < minK or x > maxK :i0 =i \n",
    "            j = min_i if min_i < max_i else max_i\n",
    "            ans += max(min(min_i,max_i)-i0,0)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        def counttimes(start,end):\n",
    "            l=start\n",
    "            r=start\n",
    "            cntmax=0\n",
    "            cntmin=0\n",
    "            ans=0\n",
    "            while r<=end:\n",
    "                if nums[r]==minK: cntmin+=1\n",
    "                if nums[r]==maxK: cntmax+=1\n",
    "                while cntmin and cntmax and l<=r:\n",
    "                    if nums[l]==minK: cntmin-=1\n",
    "                    if nums[l]==maxK: cntmax-=1\n",
    "                    l+=1\n",
    "                ans+=(r-start+1)-(r-l+1)\n",
    "                r+=1\n",
    "            return ans\n",
    "        start=0\n",
    "        cnt=0\n",
    "        for i,x in enumerate(nums):\n",
    "            if x<minK or x>maxK:\n",
    "                cur=counttimes(start,i-1)\n",
    "                cnt+=cur\n",
    "                start=i+1\n",
    "        cnt+=counttimes(start,len(nums)-1)\n",
    "        return cnt   \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        n = len(nums)\n",
    "        start_point = 0\n",
    "        idx = ans = 0\n",
    "        min_pos = max_pos = -1\n",
    "\n",
    "        while idx < n:\n",
    "            if nums[idx] < minK or nums[idx] > maxK:\n",
    "                idx += 1\n",
    "                start_point = idx\n",
    "                continue\n",
    "            if nums[idx] == minK:\n",
    "                min_pos = idx\n",
    "            if nums[idx] == maxK:\n",
    "                max_pos = idx\n",
    "\n",
    "            if min_pos <= max_pos:\n",
    "                t = min_pos - start_point + 1\n",
    "            else:\n",
    "                t = max_pos - start_point + 1\n",
    "            if t < 0:\n",
    "                t = 0\n",
    "            ans += t\n",
    "            idx += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        minIdx = -1\n",
    "        maxIdx = -1\n",
    "\n",
    "        start = -1\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] < minK or nums[i] > maxK:\n",
    "                start = -1\n",
    "                minIdx = -1\n",
    "                maxIdx = -1\n",
    "                continue\n",
    "\n",
    "            if start == -1:\n",
    "                start = i \n",
    "\n",
    "            if nums[i] == minK:\n",
    "                minIdx = i \n",
    "            \n",
    "            if nums[i] == maxK:\n",
    "                maxIdx = i\n",
    "            \n",
    "            if nums[i] == minK:\n",
    "                if maxIdx != -1:\n",
    "                    ans += maxIdx - start + 1\n",
    "            elif nums[i] == maxK:\n",
    "                if minIdx != -1:\n",
    "                    ans += minIdx - start + 1\n",
    "            else: # middle\n",
    "                if maxIdx != -1 and minIdx != -1:\n",
    "                    ans += min(maxIdx, minIdx) - start + 1 \n",
    "\n",
    "\n",
    "\n",
    "                   \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "奇了怪了，感觉这题也不是很好想啊\n",
    "如何一边遍历，一边枚举呢？\n",
    "转化-->小于k的nums[i]看作-1，大于k的nums[i]看作1，等于k的nums[i]看作0\n",
    "如果长度是奇数的话，则要求子数组和为0（可以把等于k的想办法平分），但是这样就难以哈希了\n",
    "观察题目发现没有相等的情况，赢\n",
    "如果长度是偶数，则要求子数组和为1\n",
    "\n",
    "但是但是，其实可以把两个哈希表合起来，因为两种情况相互独立，可以直接相加\n",
    "\n",
    "k的位置可以直接锁定，然后计算出左边的xx和，枚举右端点即可\n",
    "\n",
    "\n",
    "哈希的时候怎么记录下标呢？很简单，分奇偶即可\n",
    "\n",
    "'''\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]<k:nums[i]=-1\n",
    "            elif nums[i]==k:\n",
    "                nums[i]=0\n",
    "                idk=i  \n",
    "            else:nums[i]=1\n",
    "        # cnt1=Counter({0:1})\n",
    "        # cnt2=Counter({0:1})\n",
    "        cnt=Counter({0:1})\n",
    "        p_sum=0\n",
    "        for i in range(idk-1,-1,-1):\n",
    "            p_sum+=nums[i]\n",
    "            cnt[p_sum]+=1\n",
    "            # if i%2:\n",
    "            #     cnt1[p_sum]+=1\n",
    "            # else:\n",
    "            #     cnt2[p_sum]+=1\n",
    "        l_sum=0\n",
    "        ans=0\n",
    "        for i in range(idk,len(nums)):\n",
    "            l_sum+=nums[i]\n",
    "            ans+=(cnt[-l_sum]+cnt[1-l_sum])\n",
    "            # if i%2:\n",
    "            #     ans+=(cnt1[-l_sum]+cnt2[1-l_sum])\n",
    "            # else:\n",
    "            #     ans+=(cnt1[1-l_sum]+cnt2[-l_sum])\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "奇了怪了，感觉这题也不是很好想啊\n",
    "如何一边遍历，一边枚举呢？\n",
    "转化-->小于k的nums[i]看作-1，大于k的nums[i]看作1，等于k的nums[i]看作0\n",
    "如果长度是奇数的话，则要求子数组和为0（可以把等于k的想办法平分），但是这样就难以哈希了\n",
    "观察题目发现没有相等的情况，赢\n",
    "如果长度是偶数，则要求子数组和为1\n",
    "k的位置可以直接锁定，然后计算出左边的xx和，枚举右端点即可\n",
    "哈希的时候怎么记录下标呢？很简单，分奇偶即可\n",
    "\n",
    "'''\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]<k:nums[i]=-1\n",
    "            elif nums[i]==k:\n",
    "                nums[i]=0\n",
    "                idk=i  \n",
    "            else:nums[i]=1\n",
    "        cnt1=Counter({0:1})\n",
    "        cnt2=Counter({0:1})\n",
    "        p_sum=0\n",
    "        for i in range(idk-1,-1,-1):\n",
    "            p_sum+=nums[i]\n",
    "            if i%2:\n",
    "                cnt1[p_sum]+=1\n",
    "            else:\n",
    "                cnt2[p_sum]+=1\n",
    "        l_sum=0\n",
    "        ans=0\n",
    "        for i in range(idk,len(nums)):\n",
    "            l_sum+=nums[i]\n",
    "            if i%2:\n",
    "                ans+=(cnt1[-l_sum]+cnt2[1-l_sum])\n",
    "            else:\n",
    "                ans+=(cnt1[1-l_sum]+cnt2[-l_sum])\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        pos = nums.index(k)\n",
    "        # i=pos 的时候 x 是 0，直接记到 cnt 中，这样下面不是大于 k 就是小于 k\n",
    "        cnt, x = Counter({0: 1}), 0\n",
    "        for i in range(pos - 1, -1, -1):  # 从 pos-1 开始累加 x\n",
    "            x += 1 if nums[i] < k else -1\n",
    "            cnt[x] += 1\n",
    "\n",
    "        # i=pos 的时候 x 是 0，直接加到答案中，这样下面不是大于 k 就是小于 k\n",
    "        ans, x = cnt[0] + cnt[-1], 0\n",
    "        for i in range(pos + 1, len(nums)):  # 从 pos+1 开始累加 x\n",
    "            x += 1 if nums[i] > k else -1\n",
    "            ans += cnt[x] + cnt[x - 1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        pos = nums.index(k)\n",
    "        # i=pos 的时候 x 是 0，直接记到 cnt 中，这样下面不是大于 k 就是小于 k\n",
    "        cnt, x = Counter({0: 1}), 0\n",
    "        for i in range(pos - 1, -1, -1):  # 从 pos-1 开始累加 x\n",
    "            x += 1 if nums[i] < k else -1\n",
    "            cnt[x] += 1\n",
    "\n",
    "        # i=pos 的时候 x 是 0，直接加到答案中，这样下面不是大于 k 就是小于 k\n",
    "        ans, x = cnt[0] + cnt[-1], 0\n",
    "        for i in range(pos + 1, len(nums)):  # 从 pos+1 开始累加 x\n",
    "            x += 1 if nums[i] > k else -1\n",
    "            ans += cnt[x] + cnt[x - 1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        idx = nums.index(k)\n",
    "        ans = 1\n",
    "        pres = 0\n",
    "        left = Counter()\n",
    "        left[0] += 1\n",
    "        for i in range(idx - 1, -1, -1):\n",
    "            if nums[i] < k:\n",
    "                pres -= 1\n",
    "            else:\n",
    "                pres += 1\n",
    "            left[pres] += 1\n",
    "            if pres == 0 or pres == 1:\n",
    "                ans += 1\n",
    "        suf = 0\n",
    "        # print(left)\n",
    "        for i in range(idx + 1, n):\n",
    "            if nums[i] > k:\n",
    "                suf += 1\n",
    "            else:\n",
    "                suf -= 1\n",
    "            ans += left[-suf] + left[-suf + 1]\n",
    "    \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sign(self, num: int) -> int:\n",
    "        return (num > 0) - (num < 0)\n",
    "\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        kIndex = nums.index(k)\n",
    "        ans = 0\n",
    "        counts = Counter()\n",
    "        counts[0] = 1\n",
    "        sum = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            sum += self.sign(num - k)\n",
    "            if i < kIndex:\n",
    "                counts[sum] += 1\n",
    "            else:\n",
    "                prev0 = counts[sum]\n",
    "                prev1 = counts[sum - 1]\n",
    "                ans += prev0 + prev1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        pos = nums.index(k)\n",
    "        c = 0\n",
    "        ans = 0\n",
    "        cnt = Counter()\n",
    "        cnt[0] = 1\n",
    "        for i,num in enumerate(nums):\n",
    "            c += 1 if num > k else -1\n",
    "            if i == pos:c += 1\n",
    "            if i < pos:\n",
    "                cnt[c] += 1\n",
    "            else:\n",
    "                ans += cnt[c]+cnt[c-1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        pos = nums.index(k)\n",
    "        # i=pos 的时候 x 是 0，直接记到 cnt 中，这样下面不是大于 k 就是小于 k\n",
    "        cnt, x = Counter({0: 1}), 0\n",
    "        for i in range(pos - 1, -1, -1):  # 从 pos-1 开始累加 x\n",
    "            x += 1 if nums[i] < k else -1\n",
    "            cnt[x] += 1\n",
    "\n",
    "        # i=pos 的时候 x 是 0，直接加到答案中，这样下面不是大于 k 就是小于 k\n",
    "        ans, x = cnt[0] + cnt[-1], 0\n",
    "        for i in range(pos + 1, len(nums)):  # 从 pos+1 开始累加 x\n",
    "            x += 1 if nums[i] > k else -1\n",
    "            ans += cnt[x] + cnt[x - 1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        i = nums.index(k)\n",
    "        cnt = Counter()\n",
    "        ans = 1\n",
    "        x = 0\n",
    "        for v in nums[i + 1:]:\n",
    "            x += 1 if v > k else -1\n",
    "            ans += 0 <= x <= 1\n",
    "            cnt[x] += 1\n",
    "        x = 0\n",
    "        for j in range(i - 1, -1, -1):\n",
    "            x += 1 if nums[j] > k else -1\n",
    "            ans += 0 <= x <= 1\n",
    "            ans += cnt[-x] + cnt[-x + 1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sign(self, num: int) -> int:\n",
    "        return (num > 0) - (num < 0)\n",
    "\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        kIndex = nums.index(k)\n",
    "        ans = 0\n",
    "        counts = Counter()\n",
    "        counts[0] = 1\n",
    "        sum = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            sum += self.sign(num - k)\n",
    "            if i < kIndex:\n",
    "                counts[sum] += 1\n",
    "            else:\n",
    "                prev0 = counts[sum]\n",
    "                prev1 = counts[sum - 1]\n",
    "                ans += prev0 + prev1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sign(self, num: int) -> int:\n",
    "        return (num > 0) - (num < 0)\n",
    "\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        kIndex = nums.index(k)\n",
    "        ans = 0\n",
    "        counts = Counter()\n",
    "        counts[0] = 1\n",
    "        sum = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            sum += self.sign(num - k)\n",
    "            if i < kIndex:\n",
    "                counts[sum] += 1\n",
    "            else:\n",
    "                prev0 = counts[sum]\n",
    "                prev1 = counts[sum - 1]\n",
    "                ans += prev0 + prev1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sign(self, num: int) -> int:\n",
    "        return (num > 0) - (num < 0)\n",
    "\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        kIndex = nums.index(k)\n",
    "        ans = 0\n",
    "        counts = Counter()\n",
    "        counts[0] = 1\n",
    "        sum = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            sum += self.sign(num - k)\n",
    "            if i < kIndex:\n",
    "                counts[sum] += 1\n",
    "            else:\n",
    "                prev0 = counts[sum]\n",
    "                prev1 = counts[sum - 1]\n",
    "                ans += prev0 + prev1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sign(self, num: int) -> int:\n",
    "        return (num > 0) - (num < 0)\n",
    "\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        kIndex = nums.index(k)\n",
    "        ans = 0\n",
    "        counts = Counter()\n",
    "        counts[0] = 1\n",
    "        sum = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            sum += self.sign(num - k)\n",
    "            if i < kIndex:\n",
    "                counts[sum] += 1\n",
    "            else:\n",
    "                prev0 = counts[sum]\n",
    "                prev1 = counts[sum - 1]\n",
    "                ans += prev0 + prev1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        states = [Counter() for _ in range(2)]\n",
    "        offK = -1\n",
    "        nSmall, res = 0, 0\n",
    "        for off, n in enumerate(chain([float('inf')], nums)):\n",
    "            if n == k:\n",
    "                delta = nSmall*2 + 1\n",
    "                nSmall = 0\n",
    "                offK = off\n",
    "            elif n < k:\n",
    "                nSmall += 1\n",
    "            m = off - nSmall*2\n",
    "            off &= 1\n",
    "            if offK < 0:\n",
    "                states[off][m]+=1\n",
    "            else:\n",
    "                res += states[1-off][m-delta] + states[off][m-delta-1]\n",
    "                # print(off, m, m-delta, res)\n",
    "        return res\n",
    "        # nl = sl + ll\n",
    "        # nr = sr + lr\n",
    "        # sl + sr = ll + lr  if nl + nr is even\n",
    "        # sl + sr + 1 = ll + lr if nl + nr is odd\n",
    "        # sl + sr = nl - sl + nr - sr \n",
    "        # 2sl + 2sr = nl + nr. # even\n",
    "        # 2sl - nl = nr - 2sr # even\n",
    "        # 2(tsl - sl1) - (offK - off - 1) = off - offK - 2tsr\n",
    "        # 2tsl - 2sl1 + offL + 1 (+1) = offR - 2tsr\n",
    "        # 2tsl - offK + 1 - 2sl1 + off\n",
    "        # 2sl - nl + 1 = nr - 2sr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        idx = nums.index(k)\n",
    "        cnt = Counter()\n",
    "        x = 0 \n",
    "        cnt[0] = 1\n",
    "        for i in range(idx-1, -1, -1):\n",
    "            if nums[i] < k:\n",
    "                x += 1\n",
    "            else:\n",
    "                x -= 1\n",
    "            cnt[x] += 1\n",
    "        \n",
    "        res = cnt[0] + cnt[-1]\n",
    "        x = 0\n",
    "        for i in range(idx+1, len(nums)):\n",
    "            if nums[i] > k:\n",
    "                x += 1\n",
    "            else:\n",
    "                x -= 1\n",
    "            res += cnt[x] + cnt[x-1]\n",
    "\n",
    "        return res \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        pos = nums.index(k)\n",
    "        cnt, x = Counter({0:1}), 0\n",
    "        for i in range(pos - 1, -1, -1):\n",
    "            x += 1 if nums[i] < k else -1\n",
    "            cnt[x] += 1\n",
    "        ans, x = cnt[0] + cnt[-1], 0\n",
    "        for i in range(pos + 1, len(nums)):\n",
    "            x += 1 if nums[i] > k else -1\n",
    "            ans += cnt[x] + cnt[x - 1]\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        pos = nums.index(k)\n",
    "        # i=pos 的时候 x 是 0，直接记到 cnt 中，这样下面不是大于 k 就是小于 k\n",
    "        cnt, x = Counter({0: 1}), 0\n",
    "        for i in range(pos - 1, -1, -1):  # 从 pos-1 开始累加 x\n",
    "            x += 1 if nums[i] < k else -1\n",
    "            cnt[x] += 1\n",
    "\n",
    "        # i=pos 的时候 x 是 0，直接加到答案中，这样下面不是大于 k 就是小于 k\n",
    "        ans, x = cnt[0] + cnt[-1], 0\n",
    "        for i in range(pos + 1, len(nums)):  # 从 pos+1 开始累加 x\n",
    "            x += 1 if nums[i] > k else -1\n",
    "            ans += cnt[x] + cnt[x - 1]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        n=len(nums)\n",
    "        pos=nums.index(k)\n",
    "        ans=left=right=0\n",
    "        cd=Counter()\n",
    "        for i in range(pos,-1,-1):\n",
    "            left+=nums[i]<k   \n",
    "            right+=nums[i]>k    \n",
    "            if left==right or left==right-1:\n",
    "              #  print(i,left,right)\n",
    "                ans+=1\n",
    "            cd[left-right]+=1\n",
    "       # print(pos,ans,cd)\n",
    "        left=right=0\n",
    "        for i in range(pos+1,n):\n",
    "            left+=nums[i]<k   \n",
    "            right+=nums[i]>k\n",
    "          #  print(i,right-left,right-left-1)\n",
    "            ans+=cd[right-left]\n",
    "            ans+=cd[right-left-1]\n",
    "        return ans\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        cnt = [collections.defaultdict(int), collections.defaultdict(int)]\n",
    "        cnt[1][1] = 1\n",
    "        met = False\n",
    "        ans, g = 0, 0\n",
    "        for i, v in enumerate(nums):\n",
    "            if v == k:\n",
    "                met = True\n",
    "            elif v > k:\n",
    "                g += 1\n",
    "            if not met:\n",
    "                cnt[i % 2][2 * g - i] += 1\n",
    "            else:\n",
    "                ans += cnt[i % 2][2 * g - i] + cnt[1 - i % 2][2 * g - i + 1]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        pos = nums.index(k)\n",
    "        # i=pos 的时候 x 是 0，直接记到 cnt 中，这样下面不是大于 k 就是小于 k\n",
    "        cnt, x = Counter({0: 1}), 0\n",
    "        for i in range(pos - 1, -1, -1):  # 从 pos-1 开始累加 x\n",
    "            x += 1 if nums[i] < k else -1\n",
    "            cnt[x] += 1\n",
    "\n",
    "        # i=pos 的时候 x 是 0，直接加到答案中，这样下面不是大于 k 就是小于 k\n",
    "        ans, x = cnt[0] + cnt[-1], 0\n",
    "        for i in range(pos + 1, len(nums)):  # 从 pos+1 开始累加 x\n",
    "            x += 1 if nums[i] > k else -1\n",
    "            ans += cnt[x] + cnt[x - 1]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        states = [Counter() for _ in range(2)]\n",
    "        offK = -1\n",
    "        nSmall, res = 0, 0\n",
    "        for off, n in enumerate(chain([float('inf')], nums)):\n",
    "            if n == k:\n",
    "                delta = nSmall*2 + 1\n",
    "                nSmall = 0\n",
    "                offK = off\n",
    "            elif n < k:\n",
    "                nSmall += 1\n",
    "            m = off - nSmall*2\n",
    "            off &= 1\n",
    "            if offK < 0:\n",
    "                states[off][m]+=1\n",
    "            else:\n",
    "                res += states[1-off].get(m-delta, 0) + states[off].get(m-delta-1, 0)\n",
    "                # print(off, m, m-delta, res)\n",
    "        return res\n",
    "        # nl = sl + ll\n",
    "        # nr = sr + lr\n",
    "        # sl + sr = ll + lr  if nl + nr is even\n",
    "        # sl + sr + 1 = ll + lr if nl + nr is odd\n",
    "        # sl + sr = nl - sl + nr - sr \n",
    "        # 2sl + 2sr = nl + nr. # even\n",
    "        # 2sl - nl = nr - 2sr # even\n",
    "        # 2(tsl - sl1) - (offK - off - 1) = off - offK - 2tsr\n",
    "        # 2tsl - 2sl1 + offL + 1 (+1) = offR - 2tsr\n",
    "        # 2tsl - offK + 1 - 2sl1 + off\n",
    "        # 2sl - nl + 1 = nr - 2sr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        pos , n= nums.index(k), len(nums)\n",
    "        cnt, x = [0] * (n * 2), n\n",
    "        cnt[x] = 1\n",
    "        for i in range(pos - 1, -1, -1):\n",
    "            x += 1 if nums[i] < k else -1\n",
    "            cnt[x] += 1\n",
    "        ans, x = cnt[n] + cnt[n - 1], n\n",
    "        for i in range(pos + 1, len(nums)):\n",
    "            x += 1 if nums[i] > k else -1\n",
    "            ans += cnt[x] + cnt[x - 1]\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        presum = 0\n",
    "        premap = defaultdict(int)\n",
    "        premap[0] = 1\n",
    "        flag = False\n",
    "        for num in nums:\n",
    "            if num < k:\n",
    "                presum += -1\n",
    "            elif num > k:\n",
    "                presum += 1\n",
    "            else:\n",
    "                flag = True\n",
    "            if flag:\n",
    "                ans += premap[presum]\n",
    "                ans += premap[presum - 1]\n",
    "            else:\n",
    "                premap[presum] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        dic = defaultdict(int)\n",
    "        now = 0\n",
    "        while nums[now] != k:\n",
    "            now += 1\n",
    "        if now == n:\n",
    "            return 0\n",
    "        count = 0\n",
    "        temp = now\n",
    "        while True:\n",
    "            dic[count] += 1\n",
    "            now += 1\n",
    "            if now == n:\n",
    "                break\n",
    "            count += 1 if nums[now] > k else -1\n",
    "        res, count = 0, 0\n",
    "        for now in range(temp-1, -1, -1):\n",
    "            res += dic[1-count] + dic[0-count]\n",
    "            count += 1 if nums[now] > k else -1\n",
    "        return res + dic[1-count] + dic[0-count]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        pre = defaultdict(int)\n",
    "        idx = nums.index(k)\n",
    "        n = len(nums)\n",
    "        cur = ans = 0\n",
    "        pre[0] = 1\n",
    "        for i, x in enumerate(nums):\n",
    "            if x < k:\n",
    "                cur -= 1\n",
    "            elif x > k:\n",
    "                cur += 1\n",
    "            if i >= idx:\n",
    "                ans += pre[cur]\n",
    "                ans += pre[cur - 1]\n",
    "            if i < idx:\n",
    "                pre[cur] += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i] == k:\n",
    "                idx = i\n",
    "                break\n",
    "        else:\n",
    "            return 0\n",
    "        counter = [0] * (2 * n)\n",
    "        counter[0] = 1\n",
    "        bigger = 0\n",
    "        for i in range(idx + 1, n):\n",
    "            if nums[i] > k:\n",
    "                bigger += 1\n",
    "            counter[2 * bigger - (i - idx)] += 1\n",
    "            \n",
    "        less = 0\n",
    "        ret = counter[0] + counter[1]\n",
    "        for i in range(idx - 1, -1, -1):\n",
    "            if nums[i] < k:\n",
    "                less += 1\n",
    "            t = less * 2 - (idx - i)\n",
    "            ret += counter[t] + counter[t + 1]\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i] == k:\n",
    "                idx = i\n",
    "                break\n",
    "        else:\n",
    "            return 0\n",
    "        counter = Counter([0])\n",
    "        bigger = 0\n",
    "        for i in range(idx + 1, n):\n",
    "            if nums[i] > k:\n",
    "                bigger += 1\n",
    "            counter[2 * bigger - (i - idx)] += 1\n",
    "            \n",
    "        less = 0\n",
    "        ret = counter[0] + counter[1]\n",
    "        for i in range(idx - 1, -1, -1):\n",
    "            if nums[i] < k:\n",
    "                less += 1\n",
    "            t = less * 2 - (idx - i)\n",
    "            ret += counter[t] + counter[t + 1]\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        pos = nums.index(k)\n",
    "        right = Counter()\n",
    "        p1, p2 = 0, 0\n",
    "        for i in range(pos, n):\n",
    "            p1 = p1 + int(nums[i] < k)\n",
    "            p2 = p2 + int(nums[i] > k)\n",
    "            right[p1 - p2] += 1\n",
    "        ans = 0\n",
    "        p1, p2 = 0, 0\n",
    "        for i in range(pos, -1, -1):\n",
    "            p1 = p1 + int(nums[i] < k)\n",
    "            p2 = p2 + int(nums[i] > k)\n",
    "            ans += right[-(p1 - p2)] + right[-(p1 - p2) - 1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        p = nums.index(k)\n",
    "        cnt = 0\n",
    "        counter = collections.Counter()\n",
    "        counter[0] = 1 \n",
    "        for i in range(p + 1, n):\n",
    "            cnt += 1 if nums[i] >= k else - 1\n",
    "            counter[cnt] += 1 \n",
    "        res = counter[0] + counter[1]\n",
    "        cnt = 0\n",
    "        for i in range(p - 1, - 1, - 1):\n",
    "            cnt += 1 if nums[i] < k else - 1\n",
    "            res += counter[cnt] + counter[cnt + 1]\n",
    "        return res \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        counter = collections.Counter()\n",
    "        cnt = 0\n",
    "        p = nums.index(k)\n",
    "        counter[0] = 1\n",
    "        for i in range(p + 1, n):\n",
    "            cnt += 1 if nums[i] >= k else - 1 \n",
    "            counter[cnt] += 1 \n",
    "        res = counter[0] + counter[1]\n",
    "        cnt = 0\n",
    "        for i in range(p - 1, - 1, - 1):\n",
    "            cnt += 1 if nums[i] < k else - 1\n",
    "            res += counter[cnt] + counter[cnt + 1]\n",
    "        return res \n",
    "\n",
    "\n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        pre = defaultdict(int)\n",
    "        idx = nums.index(k)\n",
    "        n = len(nums)\n",
    "        cur = ans = 0\n",
    "        pre[0] = 1\n",
    "        for i, x in enumerate(nums):\n",
    "            if x < k:\n",
    "                cur -= 1\n",
    "            elif x > k:\n",
    "                cur += 1\n",
    "            if i >= idx:\n",
    "                ans += pre[cur]\n",
    "                ans += pre[cur - 1]\n",
    "            if i < idx:\n",
    "                pre[cur] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        pos, n = nums.index(k), len(nums)\n",
    "        cnt, x = [0] * (n * 2), n\n",
    "        cnt[x] = 1\n",
    "        for i in range(pos - 1, -1, -1):\n",
    "            x += 1 if nums[i] < k else -1\n",
    "            cnt[x] += 1\n",
    "\n",
    "        ans, x = cnt[n] + cnt[n - 1], n\n",
    "        for i in range(pos + 1, len(nums)):\n",
    "            x += 1 if nums[i] > k else -1\n",
    "            ans += cnt[x] + cnt[x - 1]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        counter = collections.Counter()\n",
    "        cnt = 0\n",
    "        p = nums.index(k)\n",
    "        counter[0] = 1\n",
    "        for i in range(p + 1, n):\n",
    "            cnt += 1 if nums[i] >= k else - 1 \n",
    "            counter[cnt] += 1 \n",
    "        res = counter[0] + counter[1]\n",
    "        cnt = 0\n",
    "        for i in range(p - 1, - 1, - 1):\n",
    "            cnt += 1 if nums[i] < k else - 1\n",
    "            res += counter[cnt] + counter[cnt + 1]\n",
    "        return res \n",
    "\n",
    "\n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        pos=nums.index(k)\n",
    "        cnt,c=Counter(),0\n",
    "        n=len(nums)\n",
    "        for i in range(pos,n):\n",
    "            c+=1 if nums[i]>k else -1\n",
    "            cnt[c]+=1\n",
    "        ans=c=0\n",
    "        for i in range(pos,-1,-1):\n",
    "            c+=1 if nums[i]<k else -1\n",
    "            ans+=cnt[c]+cnt[c+1]\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import *\n",
    "from queue import PriorityQueue,Queue\n",
    "from typing import *\n",
    "from heapq import *\n",
    "from functools import lru_cache,cache\n",
    "from string import *\n",
    "from itertools import product\n",
    "from collections import defaultdict\n",
    "# by hangpengjie\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        pos = 0\n",
    "        for i in range(n):\n",
    "            if nums[i] == k:\n",
    "                pos = i\n",
    "                break\n",
    "        mp = defaultdict(int)\n",
    "        mp[0] = 1\n",
    "        p = 0\n",
    "        for i in range(pos+1,n):\n",
    "            p += (1 if nums[i] > nums[pos] else -1)\n",
    "            mp[p] += 1\n",
    "        res = mp[0]+mp[1]\n",
    "        p = 0\n",
    "        for i in range(pos-1,-1,-1):\n",
    "            p += (1 if nums[i] > nums[pos] else -1)\n",
    "            res += mp[-p]+mp[-p+1]\n",
    "        return res\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
